structur metric learn high dimension problem jason davi inderjit dhillon success popular algorithm mean cluster nearest neighbor search depend assumpt underli distanc function reflect domain specif notion similar problem hand distanc metric learn problem seek optim distanc function subject constraint aris fulli supervis semisupervis inform recent algorithm propos learn distanc function low dimension set major shortcom method failur scale high dimension problem increasingli ubiquit modern data mine applic paper present metric learn algorithm scale linearli dimension permit effici optim storag evalu learn metric achiev main technic contribut framework base log determin matrix diverg enabl effici optim structur low paramet mahalanobi distanc experiment evalu method varieti high dimension domain includ text statist softwar analysi collabor filter show method scale data set ten thousand featur show learn metric achiev excel qualiti respect criteria context metric learn nearest neighbor classif show method achiev higher accuraci baselin distanc addition method yield good precis provid recal measur higher baselin method latent semant analysi 